import java.util.Scanner;

/**
 * Created with Intellij IDEA.
 * Description
 * User: wen
 * Date:2022-02-16
 * TIME:16:18
 */
public class TestDemo {
    //递归
    public static int frogJump1(int n) {
        if(n == 1 || n == 2){
            return n;
        }else{
            return frogJump1(n - 1) + frogJump1(n - 2);
        }
    }
    //迭代(循环)
    public static int frogJump2(int n) {
        if(n == 1 || n == 2){
            return n;
        }
        int f1 = 1;
        int f2 = 2;
        int f3 = 0;
        for (int i = 3; i <= n; i++) {
            f3 = f1 + f2;
            f1 = f2;
            f2 = f3;
        }
        return f3;
    }
    public static void main(String[] args) {
        System.out.println(frogJump1(1));
        System.out.println(frogJump1(2));
        System.out.println(frogJump1(3));
        System.out.println(frogJump1(4));
        System.out.println(frogJump1(5));
    }

    //-------------------------------------------------------------------------------//
    //循环(迭代)实现
    public static int fib2(int n) {
        if(n == 1 || n == 2){
            return 1;
        }
        int f1 = 1;
        int f2 = 1;
        int f3 = 0;
        for (int i = 3; i <= n; i++) {
            f3 = f1 + f2;
            f1 = f2;
            f2 = f3;
        }
        return f3;
    }
    public static void main16(String[] args) {
        System.out.println(fib2(1));
        System.out.println(fib2(2));
        System.out.println(fib2(3));
        System.out.println(fib2(4));
        System.out.println(fib2(5));
    }
    //--------------------------------------------------------------//
    public static int fib(int n) {
        if(n == 1 || n == 2){
            return 1;
        }else{
            return fib(n - 1) + fib(n - 2);
        }

    }
    public static void main15(String[] args) {
        System.out.println(fib(1));
        System.out.println(fib(2));
        System.out.println(fib(3));
        System.out.println(fib(4));
        System.out.println(fib(5));
        System.out.println(fib(6));
    }
    //----------------------------------------------------------------------------------//
    public static int sumEveryOne(int n){
        int sum = 0;
        if(n <= 9){
            return n;
        }
        else{
            return sumEveryOne(n / 10) + n % 10;
        }
    }
    public static void main14(String[] args) {
        int num = 1234;
        int ret = sumEveryOne(num);
        System.out.println( ret );
    }
    //----------------------------------------------------------------------------------//

    public static void main13(String[] args) {
        int n = 5;
        int ret = factor(n);
        System.out.println("ret = " + ret);
    }
    public static int factor(int n) {
        System.out.println("函数开始, n = " + n);
        if (n == 1) {
            System.out.println("函数结束, n = 1 ret = 1");
            return 1;
        }
        int ret = n * factor(n - 1);
        System.out.println("函数结束, n = " + n + " ret = " + ret);
        return ret;
    }



    //----------------------------------------------------------------------------------------//
    public static void printNum(int n){
        if(n <= 9){
            System.out.print(n % 10 + " ");
        }
        else{
            printNum(n / 10);
            System.out.print(n % 10 + " ");
        }
    }
    public static void main12(String[] args) {
        int num = 1234;
        printNum(num);
    }
    //-------------------------------------------------------------------------------------//
    public static int sum(int n) {
        if (n == 1){
            return 1;
        }
        else{
            return n + sum(n-1);
        }
    }
    public static void main11(String[] args) {
        int sum = 0;
        int ret = sum(3);
        System.out.println(ret);
    }
    //------------------------------------------------------------------------------------------//
    public static int fac(int n) {
        if(n == 1){
            return 1;
        }
        else{
            return n * fac(n - 1);
        }
    }
    public static void main10(String[] args) {
        System.out.println(fac(5));
    }
    //----------------------------------------------------------------------------------------//
    public static int max2(int a, int b) {
        return a > b ? a : b;
    }
    public static int max3(int a, int b, int c){
        return max2(max2(a,b),c);
    }
    public static void main9(String[] args) {
        System.out.println(max3(1,2,3));
    }
    //----------------------------------------------------------------------------------------//
    public static void main8(String[] args) {
        int[] array = { 1, 2, 3, 4, 5 };
        int left = 0;
        int right = array.length - 1;
        while(left < right){
            //left可能不止加一次，用while，不用if
            while (left < right && array[left] % 2 != 0){
                //left<right：如果1，3，5，7这种数组的话，如果不加这个限制条件，left就停不下来了，数组就会越界
                left++;
            }
            while (left < right && array[right] % 2 == 0){
                right--;
            }
            //left中是奇数，right中是偶数
            int tmp = array[left];
            array[left] = array[right];
            array[right] = tmp;
        }
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]+" ");
        }
    }
    //----------------------------------------------------------------------------------//
    public static void main7(String[] args) {
        int[] array = { 1, 2, 3, 2, 1 };
        int sum = array[0];
        for (int i = 1; i < array.length; i++) {
            sum = sum ^ array[i];
        }
    }
    //---------------------------------------------------------------------------------//
    public static void func(int n){
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j){
                    System.out.print('*');
                }
                else if (i + j == n-1){
                    System.out.print('*');
                }
                else{
                    System.out.print(" ");
                }
            }
            System.out.println();
        }
    }
    public static void main6(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextInt()){
            int n = scanner.nextInt();
            func(n);
        }
    }
    //------------------------------------------------------------------------------------------------------------//
    public static void print(int n){
        //逆序打印1234     4  3  2  1
        while (n != 0){
            System.out.print(n % 10 + " ");
            n /= 10;
        }
    }
    public static void main5(String[] args) {
        print(1234);
    }
    //---------------------------------------------------------------------------------------------------------------//
    public static void printOne(int n){
        for (int i = 30; i >= 0; i -= 2) {
            System.out.print(((n >> i) & 1) + " ");
        }
        System.out.println();
        for (int i = 31; i >= 1; i -= 2) {
            System.out.print(((n >> i) & 1) + " ");
        }
    }
    public static void main4(String[] args) {
        printOne(11);

    }
    //----------------------------------------------------------------------------------------------------------------//
    public static int numOfOne2(int n) {
        int count = 0;
        while (n != 0){
            count++;
            n = n & (n-1);
        }
        return count;
    }
    public static void main3(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int ret = scanner.nextInt();
        System.out.println(numOfOne2(ret));
    }
    //------------------------------------------------------------------------------------------------------------------//
    public static int numOfOne(int n) {
        int count = 0;
        while (n != 0){
            if((n & 1) == 1){
                count++;
            }
            n = n >>> 1;
        }
        return count;
    }
    public static void main2(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int ret = scanner.nextInt();
        System.out.println(numOfOne(ret));
    }
    //--------------------------------------------------------------------------------------------------------------//
    public static void findNum(int n){
        for (int i = 1; i <= n; i++) {
            int tmp = i;
            int count = 0;
            while (tmp != 0){
                count++;
                tmp /= 10;
            }
            //count里面存储的是输入的数字是几位数
            //tmp == 0
            tmp = i;//123
            int sum = 0;
            while (tmp != 0){
                Math.pow(tmp % 10, count);
                //sum = sum + Math.pow(tmp % 10, count);
                //pow返回值是double型，sum是整型
                //会报错，改成+=即可就解决此问题
                sum += Math.pow(tmp % 10, count);
                tmp /= 10;
            }
            if(sum == i){
                System.out.println(i);
            }

            //int count = 0;//数字的位数
            //while (i != 0){
            //    count++;
            //   i /= 10;
            //}
            //count里面存储的是输入的数字是几位数
            //有一个问题:i除完后变成0了
        }
    }

    public static void main1(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();//999999
        findNum(n);
    }
}
